#include <iostream>
#include <fstream>
#include <sstream>
#include <ctime>
#include <ratio>
#include <chrono>

const int col = 85401, elinenum = 756;
int bytenum = (col - 1) / 32 + 1;

using namespace std;

class bitmatrix {
public:
    int mycol;
    int *mybyte;

    bitmatrix() {
        mycol = -1;
        mybyte = new int[bytenum];
        for (int i = 0; i < bytenum; i++) {
            mybyte[i] = 0;
        }
    }

    bool isnull() {
        if (mycol == -1) return 1;
        return 0;
    }

    void insert(int x) {
        if (mycol == -1) mycol = x;
        int a = x / 32, b = x % 32;
        mybyte[a] |= (1 << b);
    }

    void doxor(bitmatrix b) {
        for (int i = 0; i < bytenum; i++) {
            mybyte[i] ^= b.mybyte[i];
        }
        for (int i = bytenum - 1; i >= 0; i--) {
            for (int j = 31; j >= 0; j--) {
                if ((mybyte[i] & (1 << j)) != 0) {
                    mycol = i * 32 + j;
                    return;
                }
            }
        }
        mycol = -1;
    }
};

bitmatrix *eliminer = new bitmatrix[col], *eline = new bitmatrix[elinenum];

void readdata() {
    ifstream ifs;
    ifs.open("eliminer.txt");
    string temp;
    while (getline(ifs, temp)) {
        istringstream ss(temp);
        int x;
        int trow = 0;
        while (ss >> x) {
            if (!trow) trow = x;
            eliminer[trow].insert(x);
        }
    }
    ifs.close();

    ifstream ifs2;
    ifs2.open("eline.txt");
    int trow = 0;
    while (getline(ifs2, temp)) {
        istringstream ss(temp);
        int x;
        while (ss >> x) {
            eline[trow].insert(x);
        }
        trow++;
    }
    ifs2.close();
}

void dowork() {
    for (int i = 0; i < elinenum; i++) {
        while (!eline[i].isnull()) {
            int tcol = eline[i].mycol;
            if (!eliminer[tcol].isnull())
                eline[i].doxor(eliminer[tcol]);
            else {
                eliminer[tcol] = eline[i];
                break;
            }
        }
    }
}

void printres() {
    for (int i = 0; i < elinenum; i++) {
        if (eline[i].isnull()) {
            puts("");
            continue;
        }
        for (int j = bytenum - 1; j >= 0; j--) {
            for (int k = 31; k >= 0; k--) {
                if ((eline[i].mybyte[j] & (1 << k)) != 0) {
                    printf("%d ", j * 32 + k);
                }
            }
        }
        puts("");
    }
}

int main() {
    readdata();
    using namespace std::chrono;
    high_resolution_clock::time_point t1 = high_resolution_clock::now();
    dowork();
    high_resolution_clock::time_point t2 = high_resolution_clock::now();
    cout << "serial: " << duration_cast<duration<double>>(t2 - t1).count() << endl;
    system("pause");
    return 0;
}